package com.xie.leetcode.math;

//869. 重新排序得到 2 的幂
//        给定正整数 N ，我们按任何顺序（包括原始顺序）将数字重新排序，注意其前导数字不能为零。
//
//        如果我们可以通过上述方式得到 2 的幂，返回 true；否则，返回 false。
//
//
//
//        示例 1：
//
//        输入：1
//        输出：true
//        示例 2：
//
//        输入：10
//        输出：false
//        示例 3：
//
//        输入：16
//        输出：true
//        示例 4：
//
//        输入：24
//        输出：false
//        示例 5：
//
//        输入：46
//        输出：true
//提示：
//
//        1 <= N <= 10^9

import java.math.BigDecimal;
import java.util.Arrays;

/**
 * @author xiezhendong
 * @date 2021/10/28
 */
public class ReorderedPowerOf2 {

    public static void main(String[] args) {
        ReorderedPowerOf2 reorderedPowerOf2 = new ReorderedPowerOf2();
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(1));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(10));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(16));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(24));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(46));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(1024));
        System.out.println(reorderedPowerOf2.reorderedPowerOf2(4201));
    }

    public boolean reorderedPowerOf2(int n) {
        if (check(n)) {
            return true;
        }
        int[] digitsNew = getIntegerArrays(n);
        return check2(digitsNew);
    }

    private int[] getIntegerArrays(int n) {
        BigDecimal numNew = BigDecimal.valueOf(n);
        int numNewLeng = String.valueOf(numNew).length();
        int[] digitsNew = new int[numNewLeng];
        for (int i = 0; i < numNewLeng; i++) {
            int weishu = numNewLeng - i;
            BigDecimal num10 = BigDecimal.ONE;
            for (int i1 = 1; i1 < weishu; i1++) {
                num10 = num10.multiply(BigDecimal.TEN);
            }
            BigDecimal valueLast = BigDecimal.valueOf(numNew.divide(num10.multiply(BigDecimal.TEN)).intValue()).multiply(BigDecimal.TEN);
            BigDecimal value = BigDecimal.valueOf(numNew.divide(num10).intValue()).subtract(BigDecimal.valueOf(valueLast.intValue()));
            digitsNew[i] = value.intValue();
        }
        return digitsNew;
    }

    private boolean check2(int[] digitsNew) {
        Arrays.sort(digitsNew);
        int num = 2;
        while (String.valueOf(num).length() <= digitsNew.length) {
            num = num * 2;
            if (String.valueOf(num).length() == digitsNew.length) {
                int[] nums = getIntegerArrays(num);
                Arrays.sort(nums);
                int count = 0;
                for (int i = 0; i < digitsNew.length; i++) {
                    if (nums[i] == digitsNew[i]) {
                        count++;
                    }
                }
                if (count == digitsNew.length) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean check(int n) {
        if (n == 1) {
            return true;
        }
        int num = 2;
        while (num < n) {
            num = num * 2;
        }
        return num == n;
    }
}
